#include <stdio.h>
#include <stdlib.h>

typedef struct Node{
    struct Node* children[26];
    int isEnd;
} Node;

Node* createNode(){
    Node* node = malloc(sizeof(Node));
    node->isEnd = 0;
    for(int i=0;i<26;i++){
        node->children[i] = NULL;
    }
    return node;
};

void insert(Node* root, char* word){
    int index;
    for(int i=0;word[i]!='\0';i++){
        index = word[i]-'a';
        if(!root->children[index]){
            root->children[index] = createNode();
        }
        root = root->children[index];
    }
    root->isEnd = 1;
}

int search(Node* root, char* word){
    int index;
    for(int i=0;word[i]!='\0';i++){
        index = word[i]-'a';
        if(!root->children[index]){
            return 0;
        }
        root = root->children[index];
    }
    if(root->isEnd==0){
        return 0;
    }
    return 1;
}

void freeTrie(Node* root){
    for(int i=0;i<26;i++){
        if(root->children[i]){
            freeTrie(root->children[i]);
        }
    }
    free(root);
}

int main(){
    Node* root = createNode();
    // 插入单词
    insert(root, "apple");
    insert(root, "app");
    insert(root, "bat");
     // 查找单词
     printf("Search 'apple': %d\n", search(root, "apple"));  // 输出 1
     printf("Search 'app': %d\n", search(root, "app"));      // 输出 1
     printf("Search 'bat': %d\n", search(root, "bat"));      // 输出 1
     printf("Search 'banana': %d\n", search(root, "banana"));  // 输出 0
     
     // 释放内存
     freeTrie(root);
 
     return 0;
}